package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-submatrices-with-equal-frequency-of-x-and-y/description/
 * @create 2025/8/23 14:35
 * @since JDK17
 */

public class Solution44 {
    int[][] prefix1, prefix2;
    int n, m;
    void init(int[][] prefix, char[][]grid, char x) {
        for (int a = 1, b = 0; b < n; a++, b++) {
            for (int c = 1, d = 0; d < m; c++, d++) {
                if (grid[b][d] == x) {
                    prefix[a][c] = 1;
                }
            }
        }
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= m; b++) {
                prefix[a][b] += prefix[a - 1][b] + prefix[a][b - 1] - prefix[a - 1][b - 1];
            }
        }
    }

    public int numberOfSubmatrices(char[][] grid) {
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        prefix1 = new int[n + 1][m + 1];
        prefix2 = new int[n + 1][m + 1];
        init(prefix1, grid, 'X');
        init(prefix1, grid, 'Y');
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                if (prefix1[i][j] >= 1 && prefix2[i][j] == prefix1[i][j]) {
                    ans++;
                }
            }
        }
        return ans;
    }
}
